# 12/100 子串-最小覆盖子串
# leetcode第76题: https://leetcode.cn/problems/minimum-window-substring/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/11/28
import copy
import json

from leetcode import test


def minWindow(s: str, t: str) -> str:
    m, n = len(s), len(t)
    if n > m:
        return ""

    cnt = [0] * 58  # 通过ASCII将大小写字母映射为索引
    for i in range(n):
        cnt[ord(t[i]) - 65] += 1

    def contains(s_str):
        cnt_copy = copy.deepcopy(cnt)
        """判断s的子字符串中是否包含t中的所有字符"""
        for i in range(len(s_str)):
            cnt_copy[ord(s_str[i]) - 65] -= 1
        return [num < 1 for num in cnt_copy].count(True) == 58

    start, end = 0, n
    res = ""
    min_len_sub = float('inf')
    while start < end <= m:
        sub_str = s[start:end]
        if contains(sub_str, t):
            if len(sub_str) < min_len_sub:
                res = sub_str
                min_len_sub = len(sub_str)
            else:
                start += 1
        else:
            end += 1

    return res


from collections import Counter


def minWindow_opt(s: str, t: str) -> str:
    # TODO 没整明白
    if not t or not s:
        return ""

    # 记录 t 中每个字符的频率
    t_count = Counter(t)
    required = len(t_count)

    # 滑动窗口
    l, r = 0, 0
    window_counts = {}
    formed = 0  # 记录当前窗口内满足条件的字符种类数

    # 记录最小窗口的长度和起始位置
    ans = float("inf"), None, None

    while r < len(s):
        char = s[r]
        window_counts[char] = window_counts.get(char, 0) + 1

        # 如果当前字符的频率满足 t 的需求
        if char in t_count and window_counts[char] == t_count[char]:
            formed += 1

        # 尝试收缩窗口
        while l <= r and formed == required:
            char = s[l]

            # 更新最小窗口
            if r - l + 1 < ans[0]:
                ans = (r - l + 1, l, r)

            # 缩小窗口，更新窗口内字符的频率
            window_counts[char] -= 1
            if char in t_count and window_counts[char] < t_count[char]:
                formed -= 1

            l += 1  # 左指针右移

        r += 1  # 右指针继续扩展窗口

    return "" if ans[0] == float("inf") else s[ans[1]: ans[2] + 1]


if __name__ == '__main__':
    with open("../data/d_substr3_lc76.data", "r") as file:
        lines = file.read().strip()
        jo = json.loads(lines)

    inp = [{"s": "ADOBECODEBANC", "t": "ABC"}, {"s": "a", "t": "a"}, {"s": "a", "t": "aa"},
           {"s": jo["s"], "t": jo["t"]}, ]
    out = ["BANC", "a", "", jo["ans"]]
    # test.test_function(minWindow, inp, out)  # 167.596085
    test.test_function(minWindow_opt, inp, out)  # 0.046034
